package main

import (
	"fmt"
	"math/bits"
)

//#link: https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
func main() {
	arr := []string{"un", "iq", "ue"}
	fmt.Println(maxLength(arr))
}

var ans int

func maxLength(arr []string) int {
	ans = 0
	masks := make([]int, 0)
	for _, str := range arr {
		mask := 0
		for _, c := range str {
			c -= 'a'
			//说明mask中有重复字母
			if mask>>uint(c)&1 > 0 {
				mask = 0
				break
			}
			//将c放入mask中
			mask |= 1 << uint(c)
		}
		if mask > 0 {
			masks = append(masks, mask)
		}
	}
	backTrace(0, 0, masks)
	return ans
}

func backTrace(pos, mask int, masks []int) {
	if pos == len(masks) {
		ans = max(ans, bits.OnesCount(uint(mask)))
		return
	}
	if mask&masks[pos] == 0 { // mask 和 masks[pos] 无公共元素
		//选择当前元素
		backTrace(pos+1, mask|masks[pos], masks)
	}
	//不选当前元素
	backTrace(pos+1, mask, masks)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
